
Namespace std
    Public Class hashmap(Of keyT As IComparable(Of keyT), valueT, _
                         HASH_SIZE As _int64, KEY_TO_INDEX As _to_uint32(Of keyT))
        Implements ICloneable

        Private Shared ReadOnly _end As iterator = Nothing
        Private Shared ReadOnly hashSize As Int64 = 0
        Private Shared ReadOnly _keyToIndex As KEY_TO_INDEX = Nothing
        Private _data() As map(Of keyT, valueT)

        Public Class iterator
            Inherits map(Of keyT, valueT).iterator
            Private _index As uInt32
            Private _container As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX) = Nothing

            Public Function key() As keyT
                Dim rtn As keyT = Nothing
                copy(rtn, (+p).first)
                Return rtn
            End Function

            Public Function value() As valueT
                Dim rtn As valueT = Nothing
                copy(rtn, (+p).second)
                Return rtn
            End Function

            Protected Overrides Function traversal(ByVal prev As Boolean) As Boolean
                If Not MyBase.traversal(prev) Then
                    If Not prev Then
                        _index = _container.nextIndex(_index)
                        If hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX).valid_index(_index) Then
                            p = convertor.cast(Of pointer(Of map(Of keyT, valueT).node)) _
                                              (_container.data(_index, False).begin()).instance()
                        End If

                        Return p <> _container.end()
                    Else
                        _index = _container.prevIndex(_index)
                        If hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX).valid_index(_index) Then
                            p = convertor.cast(Of pointer(Of map(Of keyT, valueT).node)) _
                                (_container.data(_index, False).rbegin()).instance()
                        End If

                        Return p <> _container.rend()
                    End If
                Else
                    Return True
                End If
            End Function

            Public Sub New(ByVal container As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX), _
                           ByVal index As Int64, _
                           ByVal that As map(Of keyT, valueT).iterator)
                MyBase.New(that)
                _container = container
                _index = index
            End Sub
        End Class

        Private Shared Function valid_index(ByVal index As UInt32) As Boolean
            Return index < hashSize
        End Function

        Private Shared Function invalid_index(ByVal index As UInt32) As Boolean
            Return Not valid_index(index)
        End Function

        Private Function data(ByVal index As Int64, Optional ByVal autoInsert As Boolean = True) As map(Of keyT, valueT)
            If _data(index) Is Nothing AndAlso autoInsert Then
                _data(index) = New map(Of keyT, valueT)()
            End If
            Return _data(index)
        End Function

        Private Function prevIndex(ByVal this As UInt32) As UInt32
            Do
                If this = 0 Then
                    this = maxUInt32
                Else
                    this -= 1
                End If
                If invalid_index(this) Then
                    Exit Do
                End If
            Loop Until Not data(this, False) Is Nothing

            Return this
        End Function

        Private Function nextIndex(ByVal this As Int32) As Int32
            Do
                this += 1
                If invalid_index(this) Then
                    Exit Do
                End If
            Loop Until Not data(this, False) Is Nothing

            Return this
        End Function

        Public Function rbegin() As iterator
            Dim rtn As iterator = Nothing
            Dim index As Int32 = prevIndex(hashSize)
            If valid_index(index) Then
                Return New iterator(Me, index, data(index).rbegin())
            End If
            Return rend()
        End Function

        Public Function begin() As iterator
            Dim rtn As iterator = Nothing
            Dim index As Int32 = nextIndex(-1)
            If valid_index(index) Then
                Return New iterator(Me, index, data(index).begin())
            End If
            Return [end]()
        End Function

        Public Function [end]() As iterator
            Return _end
        End Function

        Public Function [rend]() As iterator
            Return _end
        End Function

        Public Sub clear()
            ReDim _data(hashSize - 1)
        End Sub

        Shared Sub New()
            _end = New iterator(Nothing, npos, map(Of keyT, valueT).shared_end())
            _keyToIndex = alloc(Of KEY_TO_INDEX)()
            hashSize = +(alloc(Of HASH_SIZE)())
        End Sub

        Private Shared Function keyToIndex(ByVal k As keyT) As UInt32
            Return _keyToIndex(k) Mod hashSize
        End Function

        Public Sub New()
            clear()
        End Sub

        Default Public Property _D(ByVal k As keyT) As valueT
            Get
                Dim work As map(Of keyT, valueT).iterator = Nothing
                Dim rtn As valueT = Nothing
                Dim index As Int32 = keyToIndex(k)
                work = data(index).find(k)
                If work <> data(index).end() Then
                    Return (+work).second
                Else
                    Return Nothing
                End If
            End Get
            Set(ByVal value As valueT)
                data(keyToIndex(k)).insert(k, value)
            End Set
        End Property

        Public Function insert(ByVal k As keyT, ByVal v As valueT) As iterator
            Dim index As Int32 = npos
            index = keyToIndex(k)
            Return New iterator(Me, index, data(index).insert(k, v))
        End Function

        Public Function insert(ByVal other As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX)) As Boolean
            If other Is Nothing Then
                Return False
            Else
                For i As Int64 = 0 To hashSize - 1
                    If Not other.data(i, False) Is Nothing Then
                        data(i).insert(other.data(i))
                    End If
                Next
                Return True
            End If
        End Function

        Public Function find(ByVal k As keyT) As iterator
            Dim index As Int32 = npos
            index = keyToIndex(k)
            If data(index, False) Is Nothing Then
                Return [end]()
            Else
                Return New iterator(Me, index, data(index).find(k))
            End If
        End Function

        Public Function empty() As Boolean
            For i As Int64 = 0 To hashSize - 1
                If Not data(i, False) Is Nothing AndAlso data(i).empty() Then
                    Return False
                End If
            Next
            Return True
        End Function

        Public Function Clone() As Object Implements System.ICloneable.Clone
            Dim rtn As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX) = Nothing
            rtn = alloc(Me)
            Dim i As Int32
            For i = 0 To hashSize - 1
                If Not _data(i) Is Nothing Then
                    copy(rtn._data(i), _data(i))
                End If
            Next

            Return rtn
        End Function
    End Class
End Namespace
